package org.lyc.dp;

/**
 * 解码方法
 * https://www.bilibili.com/video/BV1aa411f7uT?p=9&vd_source=65f5ad03ccd998407c9d802ca94f29fd
 * 将字母A-Z进行编码映射
 * A -> 1
 * B -> 2
 * ...
 * Z -> 26
 * 通过给定的编码来查看总计有多少种解码方法
 * 输入: 12
 * 输出: 2
 * AB(1 2)
 * L(12)
 * <p>
 * 输入: 11106
 * 输出: 2
 * AAJF(1 1 10 6)
 * KJF(11 10 6)
 * <p>
 * 输入: 226
 * 输出: 3
 * BZ(2 26)
 * VF(22 6)
 * BBF(2 2 6)
 *
 * @author Liu Yicong
 * @date 2024/2/2
 */
public class FDecodeFunction {
	public static void main(String[] args) {
		String s = "11106";
		System.out.println(numDecodings(s));
	}

	public static int numDecodings(String s) {
		int n = s.length();
		if (n == 0 || s.charAt(0) == '0') {
			return 0;
		}

		int[] dp = new int[n + 1];
		dp[0] = 1; // 空字符串有一种解码方法（空字符串本身）
		dp[1] = 1; // 第一个字符的解码方法数量

		for (int i = 2; i <= n; i++) {
			int oneDigit = Integer.parseInt(s.substring(i - 1, i));// 选取第i个数字, 即数字s[i-1]
			int twoDigits = Integer.parseInt(s.substring(i - 2, i));// 选取前一个数字和当前数字组成的两位数s[i-2]*10 + s[i-1]

			//如果第i个数字合法则等于前一个
			if (oneDigit >= 1 && oneDigit <= 9) {
				dp[i] += dp[i - 1];
			}

			//如果两位数合法则等于前两个
			if (twoDigits >= 10 && twoDigits <= 26) {
				dp[i] += dp[i - 2];
			}
		}

		return dp[n];
	}
}
